package no15;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/25 15:00
 * 二进制 1 的个数
 * https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
 */
public class Solution {

    // 方法1. 朴素方法, 每次按位与 1, 统计次数后无符号右移
    // 缺陷: 0000000000 1 0000000 1 00000 形如这样的情况会有很多次无效检测
    public int hammingWeight01(int n) {
        // 使用位运算来统计 1 的个数
        int count = 0;
        while(n != 0) {
            if((n & 1) == 1) {
                count++;
            }
            n >>>= 1;
        }
        return count;
    }

    // 方法2. 每次 n & (n - 1) 及每次检测的都是 n 最低位的 1
    // 说明: 目前想到的最优解法
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
}
